package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

/**
 *
 * @param root TreeNode类
 * @param sum int整型
 * @return bool布尔型
 */
func hasPathSum(root *TreeNode, sum int) bool {
	// write code here
	return dfs(root, sum)
}

func dfs(root *TreeNode, sum int) bool {
	if root == nil {
		return false
	}
	sum = sum - root.Val
	if root.Left == nil && root.Right == nil {
		if sum == 0 {
			return true
		}
		return false
	}
	return dfs(root.Left, sum) || dfs(root.Right, sum)
}
